<script>
	let path = [
	[0,			1,			Infinity,	Infinity,	4],
	[1, 		0,			1,			Infinity,	Infinity],
	[Infinity, 	1, 			0, 			3, 			2],
	[Infinity, 	Infinity, 	3, 			0, 			1],
	[4, 		Infinity, 	2, 			1, 			0]
];

/* 贪心算法 */
/*
	1. 假设从1开始进行遍历，得到一串数组 arr1=[0, 20, 8]

	2. 找到arr1中最短的路径 8(3路)， 同时用一个 selected[] 保存 8索引。

	3. 遍历 3路, 当 3路 和其他的路径有通，则相当于 1路 和该路也可以通过 3路 联通，那么我们比较 1路->下路 > 1路->3路->下路。
		1. 如果成立，则可以更新 1路->下路的距离

	4. 重复 1，2，3 步骤, 遍历完成数组即可
*/

function getShort(enter) {	// i:从第几路开始, path:路径数据
	let arr1 = path[enter],	// 得到入口数据
		indexPath = {};		// 用来记录是否已经遍历


	for(let i = 0; i < arr1.length; i++) {
		let index = min(arr1, indexPath);	// 得到最小路径的索引
		if(index == -1) return arr1;		// 如果 index==-1 ，说明已经全部遍历完成
		let arr2 = path[index];				// 否则接着往下遍历
		indexPath[index] = arr1[index];		// 遍历的记录

		for(let j = 0; j < arr2.length; j++) {
			if(arr2[j]!=Infinity && (arr2[j]+arr1[index]) < arr1[j]) {
				arr1[j] = arr1[index] + arr2[j];	// 更新数组
			}
		}
	}


	return arr1;
}


function min(arr, indexArr) {
	// 得到满足要求的一个索引
	let minIndex = arr.findIndex((val, index)=>val!=0 && !indexArr[index]);
	
	// 开始遍历数组，找到最小值
	for(let i = 0; i < arr.length; i++) {
		if(arr[i] == 0) continue;
		if(arr[minIndex] >= arr[i] && !indexArr[i]) {
			minIndex = i;
		}
	}

	return minIndex;
}

let res = [];
for(let i = 0; i < path.length; i++) {
	res.push(getShort(i));
}
console.log(res);
</script>